package leetcode.Hot100;

import java.util.HashMap;

/**
 * @author Cheng Jun
 * Description: 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。、
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * 1 <= s.length, t.length <= 105
 * s 和 t 由英文字母组成
 * @version 1.0
 * @date 2021/12/28 17:04
 * 字节面试题
 */
public class minWindow {

    // 滑动窗口
    // 左右指针，先遍历找到符合目标的 L 和 R
    // 然后移动 L，移动后，若窗口不符合目标，就移动 R
    static public String minWindow(String s, String t) {
        String res = "";
        // 特殊判断
        if (s.length() < t.length()) {
            return res;
        }
        // 左右指针
        int left = 0;
        int right = 0;
        // t中各个字符出现的次数
        HashMap<Character, Integer> charCountMap = new HashMap<>();
        // 统计 t中各个字符出现的次数
        for (int i = 0; i < t.length(); i++) {
            charCountMap.put(t.charAt(i), charCountMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        // 如何更好地定义 找到了包含t的滑动窗口？
        boolean findT = false;
        for (int i = 0; i < s.length(); i++) {
            char curChar = s.charAt(i);
            // 当前元素在 charCountMap 才有可能找到了 目标窗口
            if (charCountMap.containsKey(curChar)) {
                charCountMap.put(curChar, charCountMap.get(curChar) - 1);
                // 所有的字符次数 都用光了，就是找到了
                findT = charCountMap.values().stream().allMatch(value -> value <= 0);
            }
            right++;
            // 找到后，左指针往右移动，直到不能找到窗口 不包含t
            while (findT) {
                // res 为空，直接给res 赋值
                if (res == "") {
                    res = s.substring(left, right);
                } else {
                    // 找到更小的目标窗口
                    if (res.length() > right - left) {
                        res = s.substring(left, right);
                    }
                }
                // 左指针对应的 char元素
                char leftChar = s.charAt(left);
                // 如果左指针 是t 中的元素
                if (charCountMap.containsKey(leftChar)) {
                    // 因为要左移，所以 leftChar 要加 1
                    charCountMap.put(leftChar, charCountMap.get(leftChar) + 1);
                    int count = charCountMap.get(leftChar);
                    if (count <= 0) {
                        findT = true;
                    } else {
                        findT = false;
                    }
                }
                // 不断左移 直到 findT 为false
                left++;
            }
        }
        return res;
    }
}
